home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6818 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  5.5 KB
  1. Path: uni-erlangen.de!winx03!sunshine!schoof
  2. From: schoof@informatik.uni-wuerzburg.de (Jochen Schoof)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Followup-To: comp.lang.c
  6. Date: 15 Feb 1996 14:35:42 GMT
  7. Organization: University of Wuerzburg, Germany
  8. Message-ID: <4fvgbu$kmb@winx03.informatik.uni-wuerzburg.de>
  9. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fv74c$chq@gatekeeper.alcatel.no>
  10. NNTP-Posting-Host: wi2x01.informatik.uni-wuerzburg.de
  11. X-Newsreader: TIN [version 1.2 PL2]
  12.  
  13. Sven Pran (Sven.Pran@alcatel.no) wrote:
  14. : In article <31224679.6193@born.com>, John Cleland <clelaj@born.com> wrote:
  15. : >
  16. : >Don't just strip the trailing zeros, remove all digits except the last 
  17. : >non-zero digit (which is your output) and then multiply by the next number in 
  18. : >your sequence. This keeps the numbers down to a managable level and gives the 
  19. : >correct answer as no more significant digit can affect the value of the LSD.
  20. : >
  21. :  . . . .
  22. :
  23. : No, it is obviously not sufficient to keep the last single non-zero digit, and 
  24. : the problem appears to be a very interesting and intriguing one:
  25. :
  26. : A new trailing zero is 'created' every time the next multiplier is divisible 
  27. : by 5, and how can we then calculate the next 'rightmost significant' digit?
  28. :
  29. : Example when a multiplier ends in 05:
  30. :
  31. : If the 'previous' factorial ended in 02 then the new factorial will end in 1 
  32. : while if it ended in 12 then the new factorial will end in 6 (after removal of 
  33. : trailing zeroes).
  34. :
  35. : Thus the SINGLE rightmost significant digit in the new factorial depends upon 
  36. : the TWO rightmost significant digits both in the previous factorial and in the 
  37. : multiplier.
  38. :
  39. : This means that we must keep track of the last TWO digits to calculate the new 
  40. : SINGLE rightmost significant digit whenever a zero is 'created'. For similar 
  41. : reasons we must track THREE digits to calculate the new TWO rightmost 
  42. : significant digits - and so on.
  43. :
  44. : How many zeroes have been 'removed' when we reach 1000! ? The answer is 249, 
  45. : which means that in order to maintain the precision needed we must track the 
  46. : last 250 digits less the number of zeroes already 'removed' when N! reaches a 
  47. : number with that many digits.
  48. :
  49. : This is where I get stuck. Hey - number theory specialists: How do we proceed?
  50.  
  51. I'm far from being a specialist in number theory, but as can be seen from
  52. my previous posting in this thread, have dealt with the problem for a while,
  53. too. Allow me to give some explanation why the problem can be solved by
  54. just keeping two digits stored. Assume we have two such digits m and n:
  55.  
  56.   x = 10 * m + n;  with  0<=m<=9 and 1<=n<=9
  57.  
  58. When multiplying to another number y the LSD of the result can be determined
  59. by calculating LSD(n*LSD(y)) in most cases (see tabular below). 
  60.  
  61.       n  ||  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
  62. LSD(y)   ||     |     |     |     |     |     |     |     |     |
  63. =========##=====#=====#=====#=====#=====#=====#=====#=====#=====#
  64.       1  ||  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
  65. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  66.       2  ||  2  |  4  |  6  |  8  |  *  |  2  |  4  |  6  |  8  |
  67. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  68.       3  ||  3  |  6  |  9  |  2  |  5  |  8  |  1  |  4  |  7  |
  69. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  70.       4  ||  4  |  8  |  2  |  6  |  *  |  4  |  8  |  2  |  6  |
  71. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  72.       5  ||  5  |  *  |  5  |  *  |  5  |  *  |  5  |  *  |  5  |
  73. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  74.       6  ||  6  |  2  |  8  |  4  |  *  |  6  |  2  |  8  |  2  |
  75. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  76.       7  ||  7  |  4  |  1  |  8  |  5  |  2  |  9  |  6  |  3  |
  77. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  78.       8  ||  8  |  6  |  4  |  2  |  *  |  8  |  6  |  4  |  2  |
  79. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  80.       9  ||  9  |  8  |  7  |  6  |  5  |  4  |  3  |  2  |  1  |
  81. ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  82.  
  83. We only are in trouble if one of these two is 5 and the other is even
  84. (see entries marked with *). In this case we need one more digit from 
  85. the even number to determin the new LSD of the result which is:
  86.  
  87.   LSD(n*LSD(y))+q*5   with q being either m if LSD(y)==5
  88.                         or q being the next digit from y if n==5
  89.  
  90. Storing additional digits is not neccessary. If two numbers of at least 
  91. two digits have no zeroes in their rightmost digit, the two rightmost
  92. digits of their product cannot both be zero and are determined from the
  93. two rightmost digits of the two numbers. If you don't believe me feel
  94. free to expand the tabular above for these numbers. Unfortunately you'll
  95. have to write down 8100 entries... :-)
  96.  
  97. Ans now we should probably keep this away from comp.lang.c and turn to
  98. some algorithmic group with it. Does anyone know one..?
  99.  
  100. - Jochen
  101.  
  102. --
  103. --------------------------------------------------------------------------
  104.  Jochen Schoof                  mailto:schoof@informatik.uni-wuerzburg.de
  105.  Lehrstuhl fuer Informatik II +-------------------------------------------
  106.  Universitaet Wuerzburg       | You are just reading a .sig-light:
  107.  D-97074 Wuerzburg (Germany)  | It is free of fat, sugar and cholesterol!
  108. ------------------------------+-------------------------------------------
  109.  WWW-Homepage:        http://www.informatik.uni-wuerzburg.de/staff/joscho
  110. --------------------------------------------------------------------------
  111.